הערה: המבנים כאן הם הרחבות של מבנה הנתונים האלמנטרי עץ

עץ בינארי:

• עץ שבו הדרגה של כל קודקוד היא 2 לכל היותר.
• לשני הבנים האלו נקרא בן שמאלי ובן ימני.
• עץ בינארי מלא: לכל קודקוד פנימי יש בדיוק 2 ילדים.
• עץ בינארי מושלם: הוא גם מלא וגם כל העלים בדיוק באותה רמה.
• עץ בינארי שלם: אם הוא עץ מושלם, או שהוא עץ שהיה מושלם והתחילו למחוק עלים מימין לשמאל.
• בעץ מלא, מספר הצמתים הפנימיים שווה למספר העלים פחות אחד. בעץ מלא או מושלם מספר העלים גדול ממספר הצמתים הפנימיים (הרמה האחרונה היא החלק הכבד ביותר)
• עץ חיפוש בינארי:

  • כל קודקוד בצד ימין גדול מאביו, וכל קודקוד בצד שמאל קטן מאביו.

  • כל המפתחות בבן השמאלי קטנים מהשורש, וכל המפתחות בבן הימני גדולים מהשורש.

  • קודקוד מכיל את השדות הבאים:

    • המפתח לפיו הוא מקבל מיקום בעץ.
    • מידע נוסף (אופציונלי).
    • מצביע לבן השמאלי והימני (יכולים להיות NULL).
    • מצביע לאב (אופציונלי ו - NULL עבור השורש).

  • סוגי הסריקות על העץ:

    • סריקת inorder:
      • קודם מה שבשמאל, ואז הקודקוד, ואז הימנים.
      • מתחילים מהעלה הקטן ביותר.
      • התוצאה החוזרת היא ממויינת.
      • סיבוכיות הזמן היא $\mathrm{\Theta }(n)$
    • סריקת preorder:
      • קודם הקודקוד ואז הבן השמאלי ואז הבן הימני.
    • סריקת postorder:
      • קודם בן שמאלי, ואז ימני, ואז קודקוד.
    • לדוגמא:

  • חיפוש בעץ:

    • חיפוש רקורסיבי: סיבוכיות $\mathrm{\Theta }(h)$ כאשר h הוא גובה העץ.
    • חיפוש איטרטיבי: סיבוכיות $\mathrm{\Theta }(h)$ כאשר h הוא גובה העץ.

  • הוספה לעץ:

    • נכנס כעלה, בסיבוכיות $\mathrm{\Theta }(h)$ ותוך שמירה על חוקי העץ הבינארי.

  • מחיקה מעץ:

    • במחיקה מעץ ישנן שלוש אופציות:
    1. הקודקוד הוא עלה:
       • פשוט נמחוק את הקודקוד, ללא הזזות.
    2. לקודקוד יש בן אחד:
       • נמחוק את הקודקוד, ונהפוך את הבן להיות הבן של אב הקודקוד.
    3. לקודקוד יש שני בנים:
       • נמצא מי היורש של הקודקוד (היורש גדול יותר מהקודקוד וכל הערכים שאותו קודקוד גדול מהם, אך קטן מכל השאר).
       • נמחוק את היורש ממקומו ונשים אותו במקום הקודקוד שנרצה למחוק.

מבנה עץ AVL:

• עץ חיפוש בינארי.

• התכונה החשובה של עץ מסוג זה הוא שהגובה שלו הוא לוגריתמי, לכן כל הפעולות שנבצע עליו יהיו $\mathrm{\Theta }\log (n)$.

• הוא גם בעל התכונה שכאשר נסתכל על קודקוד מסוים, הפרש הגבהים בין הבנים שלו לא יחרוג מ-1.

• פעולת Insertion:

  • נכניס עלה חדש לעץ תוך שימוש באלגוריתם ההכנסה של עץ בינארי (כדי שנשמור על תכונותיו).
  • נעלה מהעלה החדש עד לשורש, כאשר נעדכן את הגובה של כל קודקוד בדרך ונבדוק אם הוא מאוזן.
  • נעצור כאשר:
    1. הקודקוד לא מאוזן.
    2. הגובה של הקודקוד לא השתנה בעקבות ההכנסה.
    3. הקודקוד הוא השורש.
  • אם הקודקוד לא מאוזן נבצע רוטציה / רוטציה כפולה בהתאם למקרה המתאים:
  • מקרה LL(left-left):
    • ההוספה גרמה לחוסר איזון בתת העץ השמאלי של הילד השמאלי.
    • הפתרון - right rotation:
      • לוקחים את הצומת שיצא מאיזון ומורידים אותו ימינה, כך שהילד השמאלי שלו עולה ותופס את מקומו.
  • מקרה RR(right-right):
    • ההוספה גרמה לחוסר איזון בתת העץ הימני של הילד הימני.
    • הפתרון - Left rotation:
      • לוקחים את הצומת שיצא מאיזון ומורידים אותו שמאלה, כך שהילד הימני שלו עולה ותופס את מקומו.
  • מקרה LR(left-right):
    • ההוספה גרמה לחוסר איזון בתת העץ הימני של הילד השמאלי.
    • הפתרון - Double rotation (left then right):
      • קודם עושים רוטציה שמאלה על הילד השמאלי (הופכת את בעיית הLR לבעית LL)
      • לאחר מכן עושים רוטציה ימינה על הצומת הראשי שיצא מאיזון
  • מקרה RL(right-left):
    • ההוספה קרתה בתת העץ השמאלי של הילד הימני.
    • הפתרון Double rotation (right then left):
      • קודם עושים רוטציה ימינה על הילד הימני (הופכת את הבעיה הRL לבעית RR).
      • לאחר מכן עושים רוטציה שמאלה על הצומת הראשי שיצא מאיזון

• פעולת Deletion:

  • במחיקה, חשוב קודם כל לשמור על חוקי המחיקה של עץ חיפוש בינארי.
  • נעלה מהנקודה שבה נמחק הצומת בפועל לכיוון השורש, תוך עדכון גבהים ובדיקת חוסר איזון.
  • בניגוד להוספה, תיקון של חוסר איזון בקודקוד אחד באמצעות רוטציה עלול להקטין את גובהו, ולהפר את האיזון של צומת האב שלו. לכן, נצטרך לבצע מספר רוטציות למעלה כל המסלול.

עץ order statistic:

• עץ המבוסס על AVL אשר מרחיב אותו ותומך בפעולות נוספות.
• האיברים בעץ מכילים שדה נוסף size, אשר מכילה ערך מספרי של גודל תת העץ הימני + גודל תת העץ השמאלי + 1.
• פעולת Select (S,i):
  • מחזיר את האיבר מדרגה i של S (האיבר שיש i איברים קטנים ממנו).
• פעולת Rank(S,k):
  • בהינתן הערך K (שהוא מפתח של איבר הקיים ב-S), החזר את מיקומו הסדור ב-S (כמות האיברים שהוא גדול מהם).

מבנה עץ B:

• מספר הבנים חייב להיות יותר ממספר המפתחות

• באלגוריתם ההוספה, במהלך הירידה במורד העץ אם נתקלים בצומת שהוא מלא חייבים לפצל אותו לפני שממשיכים הלאה

• חוקי המבנה והגדרות:

  • המבנה מוגדר על ידי פרמטר קבוע של דרגת מינימום המסומן כ-t
  • שדות בקודקוד:
    • משתנה של כמות המפתחות.
    • מערך ממוין של המפתחות.
    • מערך מצביעים למידע עצמו.
    • מערך מצביעים לילדיו.
    • דגל בוליאני המסמן האם הוא עלה או צומת פנימי.
  • חוק העלים: תנאי ברזל הוא שכל העלים חייבים להיות בדיוק באותו העומק.
  • חוקי המפתחות:
    • חוק המינימום:
      • למעט השורש שיכול להכיל מפתח אחד, כל קודקוד חייב להכיל כמות מפתחות של לפחות: t - 1
    • חוק המקסימום:
      • כל קודקוד יכול להכיל לכל היותר כמות מפתחות של: 2t - 1
    • חוק הילדים:
      • כמות הילדים של צומת פנימי תמיד שווה לכמות המפתחות שבו ועוד אחד.

• חסמים מתמטיים וסיבוכיות חיפוש:

  • כמות המפתחות המינימלית עבור עץ שעומקו נתון: $h\le {\log }_t\frac{n+1}{2}$
  • כמות המפתחות המינימלית עבור עץ שעומקו נתון היא: $2t^h-1$
  • חיפוש:
    • בגלל מבנה הצומת, אלגוריתם החיפוש סורק או מבצע חיפוש בינארי בתוך הצומת (בזיכרון הפנימי) וקורא רק מדי פעם לדיסק.
    • כמות הגישות לדיסק נמוכה מאוד, אך זמן המעבד לחיפוש מושפע מגודל הצומת: $\mathrm{\Theta }(t{\log }_{t}n)$

• אלגוריתם הכנסה:

  • אסור להכניס מפתח חדש לקודקוד מלא.
  • במידה וצומת מלא חייב לקלוט מפתח או בן, הוא עובר פעולת פיצול:
    • המפתח החציוני מועלה אל קודקוד האב.
    • שאר המפתחות מתפצלים לשני צמתים חדשים נפרדים המשמשים כאחים, כשכל אחד מהם מכיל בדיוק: t-1.
  • שתי גישות עיקריות להכנסה:
    • מעבר יחיד (one pass):
      • כדי למנוע מצב בו אנו יורדים במורד העץ ומגלים שהעלה מלא, ואז נאלצים "לטפס" חזרה למעלה כדי לפצל, הגישה מפצלת מראש כל קודקוד מלא שנתקלים בו תוך כדי הירידה.
      • כלומר, לפני שנכנסים לצומת בסריקה מטה, בודקים אם יש בו כמות מקסימלית של מפתחות. אם כן, מפצלים אותו במקום וממשיכים לרדת אל הבן הנכון.
    • שני מעברים (two pass):
      • במקום לפצל כל מה שמלא מראש, האלגוריתם יורד במורד העץ ושומר מצביע לאב הקדמון התחתון ביותר במסלול שמחזיק לכל היותר מספר מפתחות קטן בשניים מהמקסימום.
      • אם לאחר הירידה לעלה מסתבר שהוא מלא לחלוטין ויש לפצל, האלגוריתם חוזר לאותו אב קדמון בטוח, ומבצע ממנו והלאה שרשרת פיצולים למטה לעבר העלה.
    • 

תובנות מהתרגול:

• כדי לחפש בזמן לוגריתמי נרצה שהמבנה יהיה ממוין לפי הערך שלפיו נעשה את הפעולות.
• אם נרצה מספר פעולות שדורשות חיפושים על סוגי ערכים שונים נוכל לבנות מספר מבנים וליצור מצביעים דו כיוונים ביניהם.
• טריק חשוב בפתרון בעיות הקשורות לעצים זה להוסיף שדות שמתעדכנים רק במעלה העץ (השדה בקודקוד מושפע רק מהבנים) - לדוגמא מה אורך העץ.